package unionFindSet;

import java.util.Arrays;

public class UnionFindSet {
    int[] elem;
    int useSize;

    public UnionFindSet(){//-2表示当前位置为空   -1表示为根节点  其他是父亲节点
        elem = new int[10];
        Arrays.fill(elem,-2);
    }

    public UnionFindSet(int n){
        elem = new int[n];
        Arrays.fill(elem,-2);
    }

    //添加数据
    public boolean add(int val){
        if(elem[val] != -2){
            return false;
        }
        elem[val] = -1;
        useSize++;
        return true;
    }

    //合并
    public void union(int x,int y){
        int root1 = findRoot(x);
        int root2 = findRoot(y);
        elem[root1] += elem[root2];
        elem[root2] = root1;
    }

    //查找根节点
    private int findRoot(int val) {
        if(val < 0 || val >= elem.length){
            throw new IndexOutOfBoundsException("数据越界！");
        }
        while(elem[val] >= 0){
            val = elem[val];
        }
        return val;
    }

    //判断两个数据是否在同一个集合中
    public boolean isSameSet(int x,int y){
        int root1 = findRoot(x);
        int root2 = findRoot(y);
        return  root1 == root2;
    }
    //获取集合中数据数目
    public int getCount(){
        return useSize;
    }

}
